/*
 * @lc app=leetcode.cn id=61 lang=cpp
 *
 * [61] 旋转链表
 */

#include <stack>
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
  public:
    ListNode *rotateRight(ListNode *head, int k)
    {
        std::stack<ListNode *> list_stack;
        ListNode *tmp = head;
        ListNode *new_head = nullptr;
        ListNode *pre_node = nullptr;

        while (tmp) {
            list_stack.push(tmp);
            pre_node = tmp;
            tmp = tmp->next;
        }

        if (list_stack.size() <= 1) {
            return head;
        }

        k = k % list_stack.size();
        if (k == 0) {
            return head;
        }

        pre_node->next = head;

        while (k - 1) {
            list_stack.pop();
            --k;
        }
        new_head = list_stack.top();
        list_stack.pop();
        pre_node = list_stack.top();
        pre_node->next = nullptr;

        return new_head;
    }
};
// @lc code=end
